/**
 * 1402. 统计全为 1 的正方形子矩阵
 * https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/
 */

/**
 * @param {number[][]} matrix
 * @return {number}
 */
function countSquares(matrix) {
  const { length: n } = matrix;
  const { length: m } = matrix[0];
  let count = 0;
  for (let i = 0; i < n; i += 1) {
    if (matrix[i][0] === 1) {
      count += 1;
    }
  }
  for (let j = 1; j < m; j += 1) {
    if (matrix[0][j] === 1) {
      count += 1;
    }
  }
  for (let i = 1; i < n; i += 1) {
    for (let j = 1; j < m; j += 1) {
      if (matrix[i][j] === 1) {
        matrix[i][j] = Math.min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1;
        count += matrix[i][j];
      }
    }
  }
  return count;
}

console.log(countSquares([
  [0, 1, 1, 1],
  [1, 1, 1, 1],
  [0, 1, 1, 1],
]) === 15);
console.log(countSquares([
  [1, 0, 1],
  [1, 1, 0],
  [1, 1, 0],
]) === 7);
